/*
机器人从i,j出发可以到达(i-1,j) (i+1,j) (i,j-1) (i,j+1)
子问题就是，机器人再从这(i-1,j) (i+1,j) (i,j-1) (i,j+1)出发能到达多少个格子
如果知道了子问题，原问题的解就等于所以子问题的解+1
用一个辅助数组记录当前的格子是否被访问过，一旦访问过，就说明该格子已经包含再子问题中，避免重复计算
*/
class Solution {
public:
    int sumdig(int num)
    {
        int sum=0;
        while(num)
        {
            sum+=num%10;
            num=num/10;
        }
        return sum;
    }
    int movingCount(int threshold, int rows, int cols) {
        vector<vector<bool>> vis(rows,vector<bool>(cols,false));
       int ans=dfs(0,0,rows,cols,threshold,vis);
        return ans;
    }
    int dfs(int i,int j,int r,int c,int k,vector<vector<bool>>&vis)
    {
        if(i<0||i>=r||j<0||j>=c||vis[i][j]==true||sumdig(i)+sumdig(j)>k)
            return 0;
        vis[i][j]=true;
        return 1+dfs(i,j+1,r,c,k,vis)+dfs(i, j-1, r, c, k, vis)
            +dfs(i+1,j,r,c,k,vis)+dfs(i-1,j,r,c,k,vis);
        
    }
};